package com.hy;

import java.util.LinkedList;
import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:将数组拆分成斐波那契序列
 *
 * 给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。
 *
 * 形式上，斐波那契式 序列是一个非负整数列表 f，且满足：
 *
 * 0 <= f[i] < 2^31 ，（也就是说，每个整数都符合 32 位 有符号整数类型）
 * f.length >= 3
 * 对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]
 * 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
 *
 * 返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
 *
 *
 * author: Mr.Du
 * Date: 2023/10/18
 * Time: 11:27
 */
public class SplitIntoFibonacci {

    LinkedList<Integer> res = new LinkedList<>();
    public List<Integer> splitIntoFibonacci(String num) {
        if(num.length() < 3) return res;
        if(dfs(num, 0)) return res;
        return new LinkedList<>();
    }

    public boolean dfs(String num, int start) {
        //边界条件判断，如果截取完了，并且res长度大于等于3，表示找到了一个组合。
        if (start == num.length() && res.size() >= 3) {
            return true;
        }
        for (int i = start; i < num.length(); i++) {
            //两位以上的数字不能以0开头
            if (num.charAt(start) == '0' && i > start) {
                break;
            }
            String s = num.substring(start, i + 1);
            //截取字符串转化为数字
            long cur = Long.valueOf(s);
            //如果截取的数字大于int的最大值，则终止截取
            if (cur > Integer.MAX_VALUE) {
                break;
            }
            int size = res.size();
            //如果截取的数字大于res中前两个数字的和，说明这次截取的太大，直接终止，因为后面越截取越大
            if (size >= 2) {
                if(cur > res.get(size - 1) + res.get(size - 2)){
                    break;
                }
                if(cur < res.get(size - 1) + res.get(size - 2)){
                    continue;
                }
            }
            //把数字cur添加到集合res中
            res.add((int) cur);
            //如果找到了就直接返回
            if (dfs(num, i + 1))
                return true;
            //如果没找到，就会走回溯这一步，然后把上一步添加到集合res中的数字给移除掉
            res.removeLast();
        }
        return false;
    }

}
